package bittwiddled;

import java.util.Comparator;

/**
 * Defines a {@link Comparator} based on bit-twiddling and bit-counts, with four conveniently sized implementations.
 * @author Carl A Pearson
 *
 * @param <T>
 */
public interface BankerOrder<T> extends Comparator<T> {
		
	public enum INTEGER implements BankerOrder<Integer> {
		INSTANCE {
			@Override public final int compare(Integer arg0, Integer arg1) {
				if (arg0.equals(arg1)) return 0;
				int result = Integer.bitCount(arg0) - Integer.bitCount(arg1);
				if (result != 0) return result;
				int XOR = arg0 ^ arg1;
				result = Integer.numberOfTrailingZeros(arg0 & XOR) - Integer.numberOfTrailingZeros(arg1 & XOR);
				return result;
			}
		};
		
		private static final int[] bitmask; static {
			bitmask = new int[Integer.SIZE];
			bitmask[0] = 1;
			for (int i=1; i< bitmask.length ; i++) bitmask[i] = bitmask[i-1] << 1;
		}
		
		private static final int[] moreThan; static {
			moreThan = new int[bitmask.length];
			moreThan[0]=1;
			for (int i=1; i<moreThan.length; i++) moreThan[i] = moreThan[i-1] << 1 | 1;
		}
		
		private static final int[] lessThan; static {
			lessThan = new int[bitmask.length+1];
			lessThan[0] = 0;
			lessThan[1] = 0;
			lessThan[2] = bitmask[bitmask.length-1];
			for (int i=3; i<lessThan.length; i++) lessThan[i] = lessThan[i-1] >>> 1 | lessThan[2];
		}
		
		public static int moreThan(final int howMany) {
			return moreThan[howMany];
		}
	 		
	 	public static int lessThan(final int howMany) {
	 		return lessThan[howMany];
	 	}
	 	
	 	public static int bitmask(final int which) {
	 		return bitmask[which];
	 	}
	}
	
	public enum LONG implements BankerOrder<Long> {
		INSTANCE {
			@Override public final int compare(Long arg0, Long arg1) {
				if (arg0.equals(arg1)) return 0;
				int result = Long.bitCount(arg0) - Long.bitCount(arg1);
				if (result != 0) return result;
				long XOR = arg0 ^ arg1;
				result = Long.numberOfTrailingZeros(arg0 & XOR) - Long.numberOfTrailingZeros(arg1 & XOR);
				return result;
			}
		};
		
		private static final long[] bitmask; static {
			bitmask = new long[Long.SIZE];
			bitmask[0] = 1;
			for (int i=1; i< bitmask.length ; i++) bitmask[i] = bitmask[i-1] << 1;
		}
		
		private static final long[] moreThan; static {
			moreThan = new long[bitmask.length];
			moreThan[0]=1;
			for (int i=1; i<moreThan.length; i++) moreThan[i] = moreThan[i-1] << 1 | 1;
		}
		
		private static final long[] lessThan; static {
			lessThan = new long[bitmask.length+1];
			lessThan[0] = 0;
			lessThan[1] = 0;
			lessThan[2] = bitmask[bitmask.length-1];
			for (int i=3; i<lessThan.length; i++) lessThan[i] = lessThan[i-1] >>> 1 | lessThan[2];
		}
		
		public static long moreThan(final int howMany) {
			return moreThan[howMany];
		}
	 		
	 	public static long lessThan(final int howMany) {
	 		return lessThan[howMany];
	 	}
	 	
	 	public static long bitmask(final int which) {
	 		return bitmask[which];
	 	}
	}
 		
	public enum BYTE implements BankerOrder<Byte> {

		INSTANCE {
			@Override public final int compare(Byte arg0, Byte arg1) {
				if (arg0.equals(arg1)) return 0;
				int result = bitCount(arg0) - bitCount(arg1);
				if (result != 0) return result;
				int XOR = arg0 ^ arg1;
				result = Integer.numberOfTrailingZeros(arg0 & XOR) - Integer.numberOfTrailingZeros(arg1 & XOR);
				return result;
			}
		};

		// lifted from http://mandala.co.uk/java/bitutils/BitUtils.java
		// c 2000 Tim Tyler
		private static int bitCount(byte x) {
			int temp;
			int y = (int)x;
			
			temp = 0x55;
			y = (y & temp) + (y >>> 1 & temp);
	         temp = 0x33;
	         y = (y & temp) + (y >>> 2 & temp);
	      
	         return (y & 0x07) + (y >>> 4);
		}
	   
		
		private static final byte[] bitmask; static {
			bitmask = new byte[Byte.SIZE];
			bitmask[0] = 1;
			for (int i=1; i< bitmask.length ; i++) bitmask[i] = (byte)(bitmask[i-1] << 1);
		}
		
		private static final byte[] moreThan; static {
			moreThan = new byte[bitmask.length];
			moreThan[0]=1;
			for (int i=1; i<moreThan.length; i++) moreThan[i] = (byte)(moreThan[i-1] << 1 | 1);
		}
		
		private static final byte[] lessThan; static {
			lessThan = new byte[bitmask.length+1];
			lessThan[0] = 0;
			lessThan[1] = 0;
			lessThan[2] = bitmask[bitmask.length-1];
			for (int i=3; i<lessThan.length; i++) lessThan[i] = (byte)(lessThan[i-1] >>> 1 | lessThan[2]);
		}
		
		public static byte moreThan(final int howMany) {
			return moreThan[howMany];
		}
	 		
	 	public static byte lessThan(final int howMany) {
	 		return lessThan[howMany];
	 	}
	 	
	 	public static byte bitmask(final int which) {
	 		return bitmask[which];
	 	}
	 		
	}

	public enum SHORT implements BankerOrder<Short> {

		INSTANCE {
			@Override public final int compare(Short arg0, Short arg1) {
				if (arg0.equals(arg1)) return 0;
				int result = bitCount(arg0) - bitCount(arg1);
				if (result != 0) return result;
				int XOR = arg0 ^ arg1;
				result = Integer.numberOfTrailingZeros(arg0 & XOR) - Integer.numberOfTrailingZeros(arg1 & XOR);
				return result;
			}
		};
		
		// lifted from http://mandala.co.uk/java/bitutils/BitUtils.java
		// c 2000 Tim Tyler
		private static int bitCount(short x) {
	         int temp;
	         int y = (int)x;
	      
	         temp = 0x5555;
	         y = (y & temp) + (y >>> 1 & temp);
	         temp = 0x3333;
	         y = (y & temp) + (y >>> 2 & temp);
	         temp = 0x0707;
	         y = (y & temp) + (y >>> 4 & temp);
	      
	         return (y & 0x000f) + (y >>> 8);
		}

		private static final short[] bitmask; static {
			bitmask = new short[Short.SIZE];
			bitmask[0] = 1;
			for (int i=1; i< bitmask.length ; i++) bitmask[i] = (short)(bitmask[i-1] << 1);
		}
		
		private static final short[] moreThan; static {
			moreThan = new short[bitmask.length];
			moreThan[0]=1;
			for (int i=1; i<moreThan.length; i++) moreThan[i] = (short)(moreThan[i-1] << 1 | 1);
		}
		
		private static final short[] lessThan; static {
			lessThan = new short[bitmask.length+1];
			lessThan[0] = 0;
			lessThan[1] = 0;
			lessThan[2] = bitmask[bitmask.length-1];
			for (int i=3; i<lessThan.length; i++) lessThan[i] = (short)(lessThan[i-1] >>> 1 | lessThan[2]);
		}
		
		public static short moreThan(final int howMany) {
			return moreThan[howMany];
		}
	 		
	 	public static short lessThan(final int howMany) {
	 		return lessThan[howMany];
	 	}
	 	
	 	public static short bitmask(final int which) {
	 		return lessThan[which];
	 	}
	 		
	}
}
